
import random

BSIZE=5
VOLTORB=0
EMPTY=-1

class Board:
    
    def __init__(self, empty=True):
        self.board=[]
        self.rt=[0]*5
        self.ct=[0]*5
        self.rv=[0]*5
        self.cv=[0]*5
        for i in xrange(BSIZE):
            self.board.append([-1]*5)

        if not empty:
            for i in xrange(BSIZE):
                for j in xrange(BSIZE):
                    self.board[i][j]=random.randint(0,4)

    def getRowTotal(self,row):
        return self.rt[row]

    def getColTotal(self, col):
        return self.ct[col]

    def getRowVoltorb(self, row):
        return self.rv[row]

    def getColVoltorb(self, col):
        return self.cv[col]

    def setPosition(self, x,y,value):
        #remove old value:
        if self.board[x][y]>0:
            self.ct[x]-=self.board[x][y];
            self.rt[y]-=self.board[x][y];
        elif self.board[x][y]==VOLTORB:
            self.cv[x]-=1
            self.rv[y]-=1

        #add new value
        if value>0:
            self.ct[x]+=value;
            self.rt[y]+=value;
        elif value==VOLTORB:
            self.cv[x]+=1;
            self.rv[y]+=1;

        self.board[x][y]=value
        

    def getPosition(self,x,y):
        return self.board[x][y];
    
    def duplicate(self):
        copy=Board()
        for x in xrange(BSIZE):
            for y in xrange(BSIZE):
                copy.setPosition(x,y, self.board[x][y])
        return copy

class UnknownBoard(Board):
    def __init__(self, rowTotal, colTotal, rowVoltorb, colVoltorb):
        self.rowTotal=rowTotal
        self.colTotal=colTotal
        self.rowVoltorb=rowVoltorb
        self.colVoltorb=colVoltorb

        self.getRowTotal=lambda i: self.rowTotal[i]
        self.getColTotal=lambda i: self.colTotal[i]
        self.getRowVoltorb=lambda i: self.rowVoltorb[i]
        self.getColVoltorb=lambda i: self.colVoltorb[i]

    def setPosition(self, x,y,value):
        pass

    def getPosition(self, x,y):
        return EMPTY

def boardSafe(trial, unknown, op):
    for i in xrange(BSIZE):
        if op(trial.getRowTotal(i),unknown.getRowTotal(i)) \
                and op(trial.getColTotal(i),unknown.getColTotal(i)) \
                and op(trial.getRowVoltorb(i),unknown.getRowVoltorb(i)) \
                and op(trial.getColVoltorb(i),unknown.getColVoltorb(i)):
            continue;
        else:
            return False
    return True
    

def solveBoard(sqr,trial,unknown,solutions):
    x=sqr%5
    y=sqr/5

    for v in xrange(4):
        trial.setPosition(x,y,v)

        if sqr==24: #reached last square, check the whole board
            
            if boardSafe(trial,unknown, lambda a,b: a==b):
                solutions.append(trial.duplicate())
                
        elif y==BSIZE-1: #column finished/reached last row
            if (trial.getColTotal(x)!=unknown.getColTotal(x) \
                        or trial.getColVoltorb(x)!=unknown.getColVoltorb(x)):
               continue
        elif x==BSIZE-1:# row finished/reached last col
            if (trial.getRowTotal(y)!=unknown.getRowTotal(y) \
                        or trial.getRowVoltorb(y)!=unknown.getRowVoltorb(y)):
                continue
        elif trial.getRowTotal(y)>unknown.getRowTotal(y) \
                or trial.getColTotal(x)>unknown.getColTotal(x) \
                or trial.getRowVoltorb(y)>unknown.getRowVoltorb(y) \
                or trial.getColVoltorb(x)>unknown.getColVoltorb(x):
             
             continue
       # elif not boardSafe(trial, unknown, lambda a,b: a<=b):
        #    continue
        if sqr<24:
            solveBoard(sqr+1,trial,unknown,solutions)
    trial.setPosition(x,y,EMPTY)

    return solutions
            
            
def solver( rowTotal, colTotal, rowVoltorb, colVoltorb):
    global unknown
    unknown=UnknownBoard(rowTotal, colTotal, rowVoltorb,colVoltorb)
    trial=Board()
    solutions=[]
    solveBoard(0,trial, unknown, solutions)

    return solutions

def computeExpectedBoards(solutions):
    probs=[]
    
    #initialize the boards

    #probs[x][y][v] gives the probability that square x,y has value v
    for i in xrange(BSIZE):
        probs.append([]);
        for j in xrange(BSIZE):
            probs[i].append([0.0, 0.0, 0.0, 0.0]);

    for board in solutions:
        for x in xrange(BSIZE):
            for y in xrange(BSIZE):
                probs[x][y][ board.board[x][y]] += 1.0
                    
    for x in xrange(BSIZE):
        for y in xrange(BSIZE):
            for v in range(4):
                probs[x][y][v]/=float(len(solutions))
        
    return probs;


def genericPrintBoard(formatFunc, board=None, showCoords=True):
    if showCoords:
        print " \tC0\tC1\tC2\tC3\tC4"
    for y in xrange(BSIZE):
        out="R%d\t" % y;
        for x in xrange(BSIZE):
            out+=formatFunc(x,y)+"\t"
        if board!=None:
            out+="(%d|%d)" % (board.getRowTotal(y), board.getRowVoltorb(y));
        print out;
        
    if board!=None:
        out="";
        if showCoords:
            out=" \t"
        for x in xrange(BSIZE):
            out+="(%d|%d)\t" % (board.getColTotal(x), board.getColVoltorb(x));
        print out;

    

def printBoard(board):
    genericPrintBoard( lambda x,y: "%d" % board[x][y], board);



def printProbBoard(probs, v):
    genericPrintBoard( lambda x,y: "%4.4f" %probs[x][y][v], unknown);
    

rt=[4,3,7,6,5]
ct=[7,4,7,3,4]
rv=[1,2,1,1,1]
cv=[0,1,1,2,2]


solutions=solver(rt,ct,rv,cv)

def doFilter(x,y,v):
    global solutions
    solutions=filter(lambda b: b.board[x][y]==v, solutions)
    return solutions;



# parses the input so that it's easier and faster to type
def solve(level,s):
	global rt, ct, rv, cv, solutions
	rt = []
	ct = []
	rv = []
	cv = []


        chars=list(s);

	j=0
        i=0
        while j<len(chars):
            if chars[j]==".":
                x=int( chars[j+1]+chars[j+2]);
                j+=3
            else:
                x = int(chars[j])
                j+=1
            if i < 10:
                if i % 2 == 0:
                    rt.append(x)
                else:
                    rv.append(x)
            else:
                if i % 2 == 0:
                    ct.append(x)
                else:
                    cv.append(x)
            i+=1

        solutions=solver(rt,ct,rv,cv);

        marker={};
        score=1

        while(True):
            #compute the best move
            probs=computeExpectedBoards(solutions)
            
            minProb=1.0
            bestMoves=[];
            for y in xrange(5):
                for x in xrange(5):
                    if (x,y) in marker:
                        continue;
                    if level<=0 and probs[x][y][1]==1.0:
                        continue;
                    if probs[x][y][0]<minProb:
                        bestMoves=[(x,y)]
                        minProb=probs[x][y][0]
                    elif probs[x][y][0]==minProb:
                        bestMoves.append( (x,y) );

            bestExpectation=0
            bestMove=None
            for (x,y) in bestMoves:
                expectation=probs[x][y][1]+2*probs[x][y][2]+3*probs[x][y][3];
                if expectation> bestExpectation:
                    bestMove=(x,y)
                    bestExpectation=expectation;

            (x,y)=bestMove
            #compute quit condition
            expectedNewScore=bestExpectation*score*(1.0- probs[x][y][VOLTORB]);
            if expectedNewScore<score and score>=80 and level<=0:
                print "you should stop playing"
                break;
                    
            def printHelper(x,y):
                if (x,y)==bestMove:
                    return "X"
                if (x,y) in marker:
                    return str(marker[(x,y)]);
                return "."

            genericPrintBoard( printHelper)


            result = raw_input( "what is under to %d, %d: " % (bestMove[0]+1,bestMove[1]+1));
            if result== '' :
                break;
            solutions=doFilter(bestMove[0], bestMove[1], int(result));

            level-=1
            marker[bestMove]=int(result);
            score*=int(result)
                
                



                        

def printStats():
    probs=computeExpectedBoards(solutions)

    # checks probs ad to 1
    for x in xrange(5):
        for y in xrange(5):
            assert(sum(probs[x][y])==1.0)
                

    print "\n1 point probabilities:"
    printProbBoard(probs, 1)
    print "\n2 point probabilities:"
    printProbBoard(probs, 2)
    print "\n3 point probabilities:"
    printProbBoard(probs, 3)
    print "\nvoltorb probabilities"
    printProbBoard(probs, 0)


